/**
 * 选择排序（Selection sort）
 *
 * ---------------------------------
 * 文档查看: /document/algo/sort_selection.md
 * 2021-01-22
 */
 
// import utils.Tools; // 不可以啊

public class Selection {
   public static int[] ToolsSwap(int array[], int x, int y) {
    int temp = array[x];
    array[x] = array[y];
    array[y] = temp;
    return array;
  }

  public static void SelectionSort(int[] array) {
    int length = array.length;
    for (int i = 0; i < length - 1; i ++) {
      int lastIndex = length - i - 1;
      int min = i;
      int max = lastIndex;
      for (int j = i; j < length - i - 1; j ++) {
        min = array[j] < array[min] ? j : min;
        max = array[j] > array[max] ? j : max;
      }

      if (min != i) {
        ToolsSwap(array, min, i);
      }

      if (max != lastIndex) {
        ToolsSwap(array, max, lastIndex);
      }
    }
  }

  public static void main(String[] args) {
    int data[] = {1, 4, 7, 5, 3, 2, 9};
    for (int i : data) {
			System.out.print(i + " ");
    }
    SelectionSort(data);
    System.out.println("result 首地址=" + data);
    for (int i : data) {
			System.out.print(i + " ");
    }
  }
}